package com.myc.subjects.slidingwindow;

import java.util.ArrayList;
import java.util.List;

/**
 * LeetCode题号：438
 *
 * 找到字符串中所有字母异位词
 *
 * 给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
 * 字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
 *
 * 说明：
 * 字母异位词指字母相同，但排列不同的字符串。
 * 不考虑答案输出的顺序。
 *
 * 示例 1:
 * 输入:
 * s: "cbaebabacd" p: "abc"
 * 输出:
 * [0, 6]
 * 解释:
 * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
 * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
 *
 * 示例 2:
 * 输入:
 * s: "abab" p: "ab"
 * 输出:
 * [0, 1, 2]
 * 解释:
 * 起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
 * 起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
 * 起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */


public class Xunzhaozimuyiweici {

    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
//        String s = "aaaaa";
//        String p = "aaaaaaaaa";
        Xunzhaozimuyiweici xunzhaozimuyiweici = new Xunzhaozimuyiweici();
        System.out.println(xunzhaozimuyiweici.findAnagrams2(s, p));
    }

    /**
     * 方法一：暴力法
     * 时间复杂度：O(m * n - m ^ 2) n为s的长度 m为p的长度
     * 枚举所有长度为 m 的子串，找出复合要求的子串，以每个字符的出现次数是否超过 p 中对应字符出现次数为依据
     */
    public List<Integer> findAnagrams1(String s, String p) {
        List<Integer> result = new ArrayList<>();//定义结果list

        //定义数组将p中所有字符出现频次记录下来
        int[] pArray = new int[26];
        for(int i = 0; i < p.length(); i++){
            pArray[p.charAt(i) - 'a']++;
        }

        for(int i = 0; i <= s.length() - p.length(); i++){
            int[] sArray = new int[26];//记录s中字符出现频次
            boolean isFill = true;//记录本次循环的子串是否符合要求
            for(int j = i; j < i + p.length(); j++){//遍历子串
                if(++sArray[s.charAt(j) - 'a'] > pArray[s.charAt(j) - 'a']){//如果子串中某一字符出现频次大于p中对应字符出现频次，则不符合要求
                    isFill = false;
                    break;
                }
            }
            if(isFill) result.add(i);//子串遍历完依旧符合要求则将i加入结果集
        }
        return result;
    }

    /**
     * 方法二：滑动窗口
     * 时间复杂度：O(n)
     * 参照最小覆盖子串那一题的思路，两个while循环分别控制左右指针
     * 外层循环的条件是: right <= s.length()
     * 内层循环的条件是：
     * 1.sArray[s.charAt(right - 1) - 'a'] > pArray[s.charAt(right - 1) - 'a']
     * 2。left < right
     */
    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> result = new ArrayList<>();

        int left = 0, right = 1;//定义左右指针，右指针从 1 开始

        int[] pArray = new int[26];
        for(int i = 0; i < p.length(); i++){
            pArray[p.charAt(i) - 'a']++;
        }

        int[] sArray = new int[26];

        while(right <= s.length()){//外循环控制右指针右移

            sArray[s.charAt(right - 1) - 'a']++;//right-1出字符出现频次 + 1
            //当子串中right - 1处出现频次 大于 p种对应字符出现频次时，左指针右移，需要去除这个多的字符带来的影响。这个很巧妙，这个滑动窗口的难点就在于理解这一点
            while(sArray[s.charAt(right - 1) - 'a'] > pArray[s.charAt(right - 1) - 'a'] && left < right){
                sArray[s.charAt(left)- 'a']--;//left出字符出现频次 + 1
                left++;
            }
            //当左指针移动完毕（或者压根没移动），条件依旧符合，则结果集增加左指针
            if(right - left == p.length()) result.add(left);
            right++;
        }

        return result;
    }

    /**
     * 方法三：滑动窗口（左右指针同时移动）
     * 时间复杂度：O(n)
     * 左右两个指针同时移动，相当于只跑了一次，这个方法是我自己想出来的，力扣用时 12ms ，比方法二还慢，一定有优化空间...
     */
    public List<Integer> findAnagrams3(String s, String p) {

        List<Integer> result = new ArrayList<>();

        if(s.length() < p.length()) return result;//这里注意需要先判断特殊情况，否则会出异常

        int left = 0;
        int right = p.length();
        int contribution = 0;//也是参照最小覆盖子串的思路，定义贡献值

        int[] pArray = new int[26];
        for(int i = 0; i < p.length(); i++){
            pArray[p.charAt(i) - 'a']++;
        }

        //这里需要初始化sArray
        int[] sArray = new int[26];
        for(int i = 0; i < right - left; i++){
            sArray[s.charAt(i) - 'a']++;
            if(sArray[s.charAt(i) - 'a'] <= pArray[s.charAt(i) - 'a']) contribution++;
        }

        while (right <= s.length()){
            if(contribution == p.length()){//当贡献值等于p长度的时候，结果集增加左指针
                result.add(left);
            }
            //控制贡献值增减
            if(--sArray[s.charAt(left) - 'a'] < pArray[s.charAt(left) - 'a']) contribution--;
            if(right < s.length() && ++sArray[s.charAt(right) - 'a'] <= pArray[s.charAt(right) - 'a']) contribution++;

            //左右指针同时右移
            left++;
            right++;
        }

        return result;
    }

    //这一题居然没有官方题解...
}

/**
 * 总结：
 * 1.对比最小覆盖子串那道题，在统计字符出现次数时，不仅可以使用HashMap来记录，也可以巧妙的使用数组来记录。区别在于，HashMap可以调用containsKey()方法来判断是否存在这个键，而且更容易统计出有多少个key
 * 2.这个滑动创口的起始位置看似是同时移动的，但是也可以分别移动来解决问题，难点就在于分别参透左右指针开始右移的条件 和 什么时候符合条件加入结果集。
 */